package main

// 207. 课程表
func main() {
	prerequisites := [][]int{
		{0, 1},
	}
	numCourses := 2
	finish := canFinish(numCourses, prerequisites)
	println(finish)
}

func canFinish(numCourses int, prerequisites [][]int) bool {
	// 用一个Map来存储学一门课需要的先修课程，使用BFS来解决问题
	inDegree := make([]int, numCourses) // 入度表
	outDegreeMap := make(map[int][]int) // 出度Map

	for _, pre := range prerequisites {
		inDegree[pre[0]]++
		outDegreeMap[pre[1]] = append(outDegreeMap[pre[1]], pre[0])
	}

	var queue []int

	for idx, val := range inDegree {
		if val == 0 {
			queue = append(queue, idx)
		}
	}

	for len(queue) > 0 {
		queueLen := len(queue)

		for i := 0; i < queueLen; i++ {
			course := queue[i]
			outDegrees := outDegreeMap[course]
			for _, num := range outDegrees {
				inDegree[num]--
				if inDegree[num] == 0 {
					queue = append(queue, num)
				}
			}
		}
		queue = queue[queueLen:]
	}

	for _, in := range inDegree {
		if in != 0 {
			return false
		}
	}

	return true
}

// 你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
//
//在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。
//
//例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
//请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
//
//示例 1：
//
//输入：numCourses = 2, prerequisites = [[1,0]]
//输出：true
//解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
//示例 2：
//
//输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
//输出：false
//解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
//
//提示：
//
//1 <= numCourses <= 2000
//0 <= prerequisites.length <= 5000
//prerequisites[i].length == 2
//0 <= ai, bi < numCourses
//prerequisites[i] 中的所有课程对 互不相同
